home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_200 / 244_01 / one32.c < prev    next >
Encoding:
C/C++ Source or Header  |  1987-10-24  |  6.9 KB  |  258 lines
  1.  
  2. /* ONE42.C */
  3. /* program to analyze the de Bruijn diagram of a cellular */
  4. /* automaton and report all the periodic states. */
  5. /* version for totalistic (3,2), first generation */
  6. /* [Harold V. McIntosh, 4 May 1987] */
  7.  
  8. # include <stdio.h>
  9.  
  10. # define MC    11                /* maximum number of columns */
  11. # define NS     11                /* number of distinct sums */
  12. # define NW    24                /* pause after so many lines */
  13.  
  14. char arry[3][3][3][3][3];
  15. int  rule[NS] = 0,1,0,0,1,2,1,2,3,3,1;
  16. int  nc, nl;
  17.  
  18. main() {char c; int i;
  19.  
  20. printf("Rule number:\n\n");
  21. printf("0....1....2\n");
  22. for (i=0; i<NS; i++) rule[i]=getchar()-'0';
  23.  
  24. nc=0;
  25. nl=0;
  26.  
  27. do {
  28. printf("  a=still  b=slowglider  c=fastglider  0,1,2=constant  q=quit\015");
  29. c=kbdin();
  30. if (c=='q') break;
  31. switch (c) {
  32. case 'a':
  33. kwait(0); printf("Sequences satisfying the condition (1,0):"); kwait(0);
  34. pass1a(); pass2i(); pass2o(); pass4(); break;
  35. case 'b':
  36. kwait(0); printf("Sequences satisfying the condition (1,1):"); kwait(0);
  37. pass1b(); pass2i(); pass2o(); pass4(); break;
  38. case 'c':
  39. kwait(0); printf("Sequences satisfying the condition (1,2):"); kwait(0);
  40. pass1c(); pass2i(); pass2o(); pass4(); break;
  41. case '0':
  42. kwait(0); printf("Sequences mapping into a constant string of 0's:"); kwait(0);
  43. pass1x(0); pass2i(); pass2o(); pass4(); break;
  44. case '1':
  45. kwait(0); printf("Sequences mapping into a constant string of 1's:"); kwait(0);
  46. pass1x(1); pass2i(); pass2o(); pass4(); break;
  47. case '2':
  48. kwait(0); printf("Sequences mapping into a constant string of 2's:"); kwait(0);
  49. pass1x(2); pass2i(); pass2o(); pass4(); break;
  50. default: break; };
  51.  } while (i!='q');
  52.  
  53. } /* end main */
  54.  
  55. /* mark all links satisfying the criterion (1,0) */
  56. pass1a() {int i0,i1,i2,i3,i4
  57. printf(" pass1a\015");
  58. for (i0=0; i0<3; i0++) {
  59. for (i1=0; i1<3; i1++) {
  60. for (i2=0; i2<3; i2++) {
  61. for (i3=0; i3<3; i3++) {
  62. for (i4=0; i4<3; i4++) {
  63. arry[i0][i1][i2][i3][i4]=rule[i0+i1+i2+i3+i4]==i2?'Y':'N';
  64. };};};};};
  65. }
  66.  
  67. /* mark all links satisfying the criterion (1,1) */
  68. pass1b() {int i0,i1,i2,i3,i4
  69. printf(" pass1b\015");
  70. for (i0=0; i0<3; i0++) {
  71. for (i1=0; i1<3; i1++) {
  72. for (i2=0; i2<3; i2++) {
  73. for (i3=0; i3<3; i3++) {
  74. for (i4=0; i4<3; i4++) {
  75. arry[i0][i1][i2][i3][i4]=rule[i0+i1+i2+i3+i4]==i1?'Y':'N';
  76. };};};};};
  77. }
  78.  
  79. /* mark all links satisfying the criterion (1,2) */
  80. pass1c() {int i0,i1,i2,i3,i4
  81. printf(" pass1c\015");
  82. for (i0=0; i0<3; i0++) {
  83. for (i1=0; i1<3; i1++) {
  84. for (i2=0; i2<3; i2++) {
  85. for (i3=0; i3<3; i3++) {
  86. for (i4=0; i4<3; i4++) {
  87. arry[i0][i1][i2][i3][i4]=rule[i0+i1+i2+i3+i4]==i0?'Y':'N';
  88. };};};};};
  89. }
  90.  
  91. /* Pass 1x marks all the configurations mapping into a constant */
  92. pass1x(c) int c; {int i0,i1,i2,i3,i4;
  93. printf(" Pass1x\015");
  94. for (i0=0; i0<3; i0++) {
  95. for (i1=0; i1<3; i1++) {
  96. for (i2=0; i2<3; i2++) {
  97. for (i3=0; i3<3; i3++) {
  98. for (i4=0; i4<3; i4++) {
  99. arry[i0][i1][i2][i3][i4]=rule[i0+i1+i2+i3+i4]==c?'Y':'N';
  100.   };};};};}; }
  101.  
  102. /* flag links which have an incoming arrow */
  103. pass2i() {int i0, i1, i2, i3, i4, m;
  104. do {
  105. printf(" pass2i\015");
  106. for (i0=0; i0<3; i0++) {
  107. for (i1=0; i1<3; i1++) {
  108. for (i2=0; i2<3; i2++) {
  109. for (i3=0; i3<3; i3++) {
  110. for (i4=0; i4<3; i4++) {
  111. if ((arry[i0][i1][i2][i3][i4]&0x5F)=='Y')
  112.  {for (m=0; m<3; m++) arry[i1][i2][i3][i4][m]|=0x20;};
  113. };};};};};
  114. } while (pass3()!=0);
  115. }
  116.  
  117. /* flag links which have an outgoing arrow */
  118. pass2o() {int i0, i1, i2, i3, i4, m;
  119. do {
  120. printf(" pass2o\015");
  121. for (i0=0; i0<3; i0++) {
  122. for (i1=0; i1<3; i1++) {
  123. for (i2=0; i2<3; i2++) {
  124. for (i3=0; i3<3; i3++) {
  125. for (i4=0; i4<3; i4++) {
  126. if ((arry[i0][i1][i2][i3][i4]&0x5F)=='Y')
  127.  {for (m=0; m<3; m++) arry[m][i0][i1][i2][i3]|=0x20;};
  128. };};};};};
  129. } while(pass3()!=0);
  130. }
  131.  
  132. /* erase flags, mark survivors, count channges */
  133. pass3() {int i0, i1, i2, i3, i4, l;
  134. l=0;
  135. printf(" pass3 \015");
  136. for (i0=0; i0<3; i0++) {
  137. for (i1=0; i1<3; i1++) {
  138. for (i2=0; i2<3; i2++) {
  139. for (i3=0; i3<3; i3++) {
  140. for (i4=0; i4<3; i4++) {
  141. switch (arry[i0][i1][i2][i3][i4]) {
  142.     case 'y': arry[i0][i1][i2][i3][i4]='Y'; break;
  143.     case 'Y': arry[i0][i1][i2][i3][i4]='N'; l=1; break;
  144.     case 'n': case 'N': arry[i0][i1][i2][i3][i4]='N'; break;
  145.     default: break; };
  146. };};};};};
  147. return l;
  148. }
  149.  
  150. /* pass4 - print loops which remain */
  151. pass4() {
  152. int i0, i1, i2, i3, i4;
  153. int j0, j1, j2, j3, j4, k, l, m;
  154. printf(" pass4 \015");
  155. for (i0=0; i0<3; i0++) {
  156. for (i1=0; i1<3; i1++) {
  157. for (i2=0; i2<3; i2++) {
  158. for (i3=0; i3<3; i3++) {
  159. for (i4=0; i4<3; i4++) {
  160. j1=i1; j2=i2; j3=i3; j4=i4; l=0; m=0;
  161. do {
  162.         if (arry[0][j1][j2][j3][j4]=='Y')
  163.     {arry[0][j1][j2][j3][j4]='y';
  164.     k=j4; j4=j3; j3=j2; j2=j1; j1=0; m=1;}
  165.   else {if (arry[1][j1][j2][j3][j4]=='Y')
  166.     {arry[1][j1][j2][j3][j4]='y';
  167.     k=j4; j4=j3; j3=j2; j2=j1; j1=1; m=1;}
  168.   else {if (arry[2][j1][j2][j3][j4]=='Y')
  169.     {arry[2][j1][j2][j3][j4]='y';
  170.     k=j4; j4=j3; j3=j2; j2=j1; j1=2; m=1;}
  171.   else {l=1; if(m==1) {j0=j1; j1=j2; j2=j3; j3=j4; j4=k;}; };};};
  172.   } while (l==0);
  173. l=0; 
  174. m=0;
  175. do {
  176.         if (arry[j0][j1][j2][j3][0]=='y')
  177.    {prf(j0,j1,j2,j3,0);
  178.    arry[j0][j1][j2][j3][0]='N';
  179.    j0=j1; j1=j2; j2=j3; j3=0; m=1;}
  180.   else {if (arry[j0][j1][j2][j3][1]=='y')
  181.    {prf(j0,j1,j2,j3,1);
  182.    arry[j0][j1][j2][j3][1]='N';
  183.    j0=j1; j1=j2; j2=j3; j3=1; m=1;}
  184.   else {if (arry[j0][j1][j2][j3][2]=='y')
  185.    {prf(j0,j1,j2,j3,2);
  186.    arry[j0][j1][j2][j3][2]='N';
  187.    j0=j1; j1=j2; j2=j3; j3=2; m=1;}
  188.   else {l=1;};};};
  189.   } while (l==0);
  190. l=0;
  191. do {
  192.         if (arry[j0][j1][j2][j3][0]=='Y')
  193.    {prf(j0,j1,j2,j3,0);
  194.    arry[j0][j1][j2][j3][0]='N';
  195.    j0=j1; j1=j2; j2=j3; j3=0; m=1;}
  196.   else {if (arry[j0][j1][j2][j3][1]=='Y')
  197.    {prf(j0,j1,j2,j3,1);
  198.    arry[j0][j1][j2][j3][1]='N';
  199.    j0=j1; j1=j2; j2=j3; j3=1; m=1;}
  200.   else {if (arry[j0][j1][j2][j3][2]=='Y')
  201.    {prf(j0,j1,j2,j3,2);
  202.    arry[j0][j1][j2][j3][2]='N';
  203.    j0=j1; j1=j2; j2=j3; j3=2; m=1;}
  204.   else {l=1; if (m==1) kwait(0);};};};
  205.   } while (l==0);
  206. };};};};};
  207. }
  208.  
  209. /* print one link of the de Bruijn diagram */
  210. prf(i0,i1,i2,i3,i4) int i0, i1,i2, i3, i4; {
  211. kwait(1);
  212. printf("%1d",i0);
  213. printf("%1d",i1);
  214. printf("%1d",i2);
  215. printf("%1d",i3);
  216. printf("-");
  217. printf("%1d",i4);
  218. printf(" ");}
  219.  
  220. /* print the entire array of links */
  221. /* feasible only during debugging  */
  222. pall() {
  223. int i0, i1, i2, i3, i4;
  224. for (i0=0; i0<3; i0++) {
  225. for (i1=0; i1<3; i1++) {
  226. for (i2=0; i2<3; i2++) {
  227. for (i3=0; i3<3; i3++) {
  228. for (i4=0; i4<3; i4++) {
  229. printf("%c",arry[i0][i1][i2][i3][i4]);
  230. };};};};};
  231. printf("\n");
  232. }
  233.  
  234. /* keyboard status */
  235. kbdst() {return bdos(11)&0xFF;}
  236.  
  237. /* direct keyboard input, no echo */
  238. kbdin() {int c;
  239. if ((c=bdos(7)&0xFF)=='\0') c=(bdos(7)&0xFF)|0x80;
  240. return c;}
  241.  
  242. /* pause at the end of a full screen */
  243. kwait(i) int i; {
  244. switch (i) {
  245.   case 0: printf("\n"); nc=0; nl++; break;
  246.   case 1: if (nc==MC) {printf("&\n"); nc=1; nl++;} else nc++; break;
  247.   default: break;};
  248. if (nl==NW) {
  249.   nl=0;
  250.   printf(" press any key to continue\015");
  251.   while (kbdst()) {};
  252.   kbdin();
  253.   printf("-                         \n");
  254.   };
  255. }
  256.  
  257. /* end */
  258.